SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Simon's problem</title>

</head>

Simon's problem

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Not to be confused with <a href="Simon_problems" title="Simon problems">Simon problems</a> in mathematical physics.</div>

In <a href="Computational_complexity_theory" title="Computational complexity theory">computational complexity theory</a> and <a href="Quantum_computing" title="Quantum computing">quantum computing</a>, Simon's problem is a <a href="Computational_problem" title="Computational problem">computational problem</a> that is proven to be solved exponentially faster on a <a href="Quantum_computer" class="mw-redirect" title="Quantum computer">quantum computer</a> than on a classical (that is, traditional) computer. The quantum algorithm solving Simon's problem, usually called Simon's algorithm, served as the inspiration for <a href="Shor's_algorithm" title="Shor's algorithm">Shor's algorithm</a>.<a href="#cite_note-1">[1]</a> Both problems are special cases of the abelian <a href="Hidden_subgroup_problem" title="Hidden subgroup problem">hidden subgroup problem</a>, which is now known to have efficient quantum algorithms.

The problem is set in the model of <a href="Decision_tree_complexity" class="mw-redirect" title="Decision tree complexity">decision tree complexity</a> or query complexity and was conceived by Daniel R. Simon in 1994.<a href="#cite_note-2">[2]</a> Simon exhibited a <a href="Quantum_algorithm" title="Quantum algorithm">quantum algorithm</a> that solves Simon's problem exponentially faster with exponentially fewer queries than the best <a href="Probabilistic_algorithms" class="mw-redirect" title="Probabilistic algorithms">probabilistic</a> (or deterministic) classical algorithm. In particular, Simon's algorithm uses a linear number of queries and any classical probabilistic algorithm must use an exponential number of queries.

This problem yields an oracle separation between the complexity classes <a href="BPP_(complexity)" title="BPP (complexity)">BPP</a> (bounded-error classical query complexity) and <a href="BQP" title="BQP">BQP</a> (bounded-error quantum query complexity).<a href="#cite_note-3">[3]</a> This is the same separation that the <a href="Bernstein%E2%80%93Vazirani_algorithm" title="Bernstein–Vazirani algorithm">Bernstein–Vazirani algorithm</a> achieves, and different from the separation provided by the <a href="Deutsch%E2%80%93Jozsa_algorithm" title="Deutsch–Jozsa algorithm">Deutsch–Jozsa algorithm</a>, which separates <a href="P_(complexity)" title="P (complexity)">P</a> and <a href="EQP_(complexity)" class="mw-redirect" title="EQP (complexity)">EQP</a>. Unlike the Bernstein–Vazirani algorithm, Simon's algorithm's separation is exponential.

Because this problem assumes the existence of a highly-structured "black box" oracle to achieve its speedup, this problem has little practical value.<a href="#cite_note-4">[4]</a> However, without such an oracle, exponential speedups cannot easily be proven, since this would prove that <a href="P_(complexity)" title="P (complexity)">P</a> is different from <a href="PSPACE" title="PSPACE">PSPACE</a>.

<div class="mw-heading mw-heading2"><h2 id="Problem_description">Problem description</h2></div>

Simon's problem considers access to a function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:\{0,1\}^{n}\to \{0,1\}^{m},\;m\geq n}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:\{0,1\}^{n}\to \{0,1\}^{m},\;m\geq n}</annotation>

</semantics>

</math><img src="./7c250601318a085f9f9a03f9212727a3ea6f9522.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.304ex; height:2.843ex;" alt="{\displaystyle f:\{0,1\}^{n}\to \{0,1\}^{m},\;m\geq n}" loading="lazy"> as implemented by a <a href="Black_box" title="Black box">black box</a> or an oracle. This function is promised to be either a <a href="Injective" class="mw-redirect" title="Injective">one-to-one</a> function, or a two-to-one function; if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is two-to-one, it is furthermore promised that two inputs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x'}</annotation>

</semantics>

</math><img src="./0ac74959896052e160a5953102e4bc3850fe93b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.014ex; height:2.509ex;" alt="{\displaystyle x'}" loading="lazy"> evaluate to the same value if and only if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x'}</annotation>

</semantics>

</math><img src="./0ac74959896052e160a5953102e4bc3850fe93b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.014ex; height:2.509ex;" alt="{\displaystyle x'}" loading="lazy"> differ in a fixed set of bits. I.e.,

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is not one-to-one, it is promised that there exists a non-zero <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> such that, for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\neq x'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\neq x'}</annotation>

</semantics>

</math><img src="./2c6cfab4b1bd197bfe3d7b6ff190cd3ae73f0368.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.443ex; height:3.009ex;" alt="{\displaystyle x\neq x'}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)=f(x')}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)=f(x')}</annotation>

</semantics>

</math><img src="./cfbc55981c8e3a0f06edcb2b2c857a4e682a9dd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.618ex; height:3.009ex;" alt="{\displaystyle f(x)=f(x')}" loading="lazy"> if and only if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x'=x\oplus s}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x'=x\oplus s}</annotation>

</semantics>

</math><img src="./68691534790b4100d03cad7134d1aee533198f23.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.373ex; height:2.676ex;" alt="{\displaystyle x'=x\oplus s}" loading="lazy"></dd></dl>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \oplus }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \oplus }</annotation>

</semantics>

</math><img src="./8b16e2bdaefee9eed86d866e6eba3ac47c710f60.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \oplus }" loading="lazy"> denotes <a href="XOR" class="mw-redirect" title="XOR">bitwise exclusive-or</a>. Simon's problem asks, in its decision version, whether <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is one-to-one or two-to-one. In its non-decision version, Simon's problem asks whether <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is one-to-one or what is the value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> (as defined above). The goal is to solve this task with the least number of queries (evaluations) of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy">.

Note that if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x'=x}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x'=x}</annotation>

</semantics>

</math><img src="./62cc09be3190c7464511712d6a1ba96481f83fa2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.443ex; height:2.509ex;" alt="{\displaystyle x'=x}" loading="lazy">, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x')=f(x)}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x')=f(x)}</annotation>

</semantics>

</math><img src="./7ca58540f95bbafee8db0387bec21f0939fee253.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.618ex; height:3.009ex;" alt="{\displaystyle f(x')=f(x)}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x'=x\oplus s}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x'=x\oplus s}</annotation>

</semantics>

</math><img src="./68691534790b4100d03cad7134d1aee533198f23.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.373ex; height:2.676ex;" alt="{\displaystyle x'=x\oplus s}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=0}</annotation>

</semantics>

</math><img src="./7903b8069a44c70f6f96511675bdd9a4ff200ed7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.351ex; height:2.176ex;" alt="{\displaystyle s=0}" loading="lazy">. On the other hand (because <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\oplus b\oplus b=a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\oplus b\oplus b=a}</annotation>

</semantics>

</math><img src="./72b11273ad9677d8b3bfc4e6d43b821174243b19.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:13.234ex; height:2.343ex;" alt="{\displaystyle a\oplus b\oplus b=a}" loading="lazy"> for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy">), <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x'=x\oplus s\iff x'\oplus x=s}">

<msup>

</msup>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x'=x\oplus s\iff x'\oplus x=s}</annotation>

</semantics>

</math><img src="./189b1034755fc88c3526c541e54de3c2efc7e8dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:27.644ex; height:2.676ex;" alt="{\displaystyle x'=x\oplus s\iff x'\oplus x=s}" loading="lazy">. Thus, Simon's problem may be restated in the following form:

<dl><dd>Given black-box or oracle access to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy">, promised to satisfy, for some <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> and all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x,x'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x,x'}</annotation>

</semantics>

</math><img src="./868106c4dab7e143519d80dfb0ce9ca91f367330.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.378ex; height:2.843ex;" alt="{\displaystyle x,x'}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)=f(x')}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)=f(x')}</annotation>

</semantics>

</math><img src="./cfbc55981c8e3a0f06edcb2b2c857a4e682a9dd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.618ex; height:3.009ex;" alt="{\displaystyle f(x)=f(x')}" loading="lazy"> if and only if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x'\oplus x\in \{0,s\}}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x'\oplus x\in \{0,s\}}</annotation>

</semantics>

</math><img src="./9385854552bf7ac0da4a12204c15eef5d051d4e8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.637ex; height:3.009ex;" alt="{\displaystyle x'\oplus x\in \{0,s\}}" loading="lazy">, determine whether <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s\neq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s\neq 0}</annotation>

</semantics>

</math><img src="./b696e0b457eecf592be8e2fda417810807613c99.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.351ex; height:2.676ex;" alt="{\displaystyle s\neq 0}" loading="lazy"> (decision version), or output <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> (non-decision version).</dd></dl>

Note also that the promise on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> implies that if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is two-to-one then it is a periodic function:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)=f(y)=f(x\oplus s).}</annotation>

</semantics>

</math><img src="./c7d104bdb33814e5a3f281c9ed049f2ca87b359b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.853ex; height:2.843ex;" alt="{\displaystyle f(x)=f(y)=f(x\oplus s).}" loading="lazy">

<div class="mw-heading mw-heading3"><h3 id="Example">Example</h3></div>

The following function is an example of a function that satisfies the required property for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=3}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=3}</annotation>

</semantics>

</math><img src="./1c5a5a42ced00df920fad4ab2d4acdb960a4105b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.656ex; height:2.176ex;" alt="{\displaystyle n=3}" loading="lazy">:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">

</th>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation>

</semantics>

</math><img src="./202945cce41ecebb6f643f31d119c514bec7a074.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}" loading="lazy">

</th></tr>

<tr>

<td>000

</td>

<td>101

</td></tr>

<tr>

<td>001

</td>

<td>010

</td></tr>

<tr>

<td>010

</td>

<td>000

</td></tr>

<tr>

<td>011

</td>

<td>110

</td></tr>

<tr>

<td>100

</td>

<td>000

</td></tr>

<tr>

<td>101

</td>

<td>110

</td></tr>

<tr>

<td>110

</td>

<td>101

</td></tr>

<tr>

<td>111

</td>

<td>010

</td></tr></tbody></table>

In this case, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=110}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=110}</annotation>

</semantics>

</math><img src="./c67af163dd96719cefee4bbd5e22aa0db31de685.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.676ex; height:2.176ex;" alt="{\displaystyle s=110}" loading="lazy"> (i.e. the solution). Every output of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> occurs twice, and the two input strings corresponding to any one given output have bitwise XOR equal to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=110}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=110}</annotation>

</semantics>

</math><img src="./c67af163dd96719cefee4bbd5e22aa0db31de685.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.676ex; height:2.176ex;" alt="{\displaystyle s=110}" loading="lazy">.

For example, the input strings <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 010}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 010}</annotation>

</semantics>

</math><img src="./3180a39e7c7e0d3db5ba787cf150f12c160a5997.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.487ex; height:2.176ex;" alt="{\displaystyle 010}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 100}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 100}</annotation>

</semantics>

</math><img src="./0572cd017c6d7936a12737c9d614a2f801f94a36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.487ex; height:2.176ex;" alt="{\displaystyle 100}" loading="lazy"> are both mapped (by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy">) to the same output string <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 000}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 000}</annotation>

</semantics>

</math><img src="./5e4fc6c26318e380f08d4ace964300ab36ebc789.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.487ex; height:2.176ex;" alt="{\displaystyle 000}" loading="lazy">. That is, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\displaystyle f(010)=000}}">

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\displaystyle f(010)=000}}</annotation>

</semantics>

</math><img src="./12086860e29e3e42d462dd01de6a7280616c4da6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.161ex; height:2.843ex;" alt="{\displaystyle {\displaystyle f(010)=000}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\displaystyle f(100)=000}}">

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\displaystyle f(100)=000}}</annotation>

</semantics>

</math><img src="./39fec3153f224e375f3d33afc7f86f5a7a327e20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.161ex; height:2.843ex;" alt="{\displaystyle {\displaystyle f(100)=000}}" loading="lazy">. Applying XOR to 010 and 100 obtains 110, that is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\displaystyle 010\oplus 100=110=s}.}">

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\displaystyle 010\oplus 100=110=s}.}</annotation>

</semantics>

</math><img src="./72ff479c7112c5f30896ab754d8399ccc202cfe6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:21.237ex; height:2.343ex;" alt="{\displaystyle {\displaystyle 010\oplus 100=110=s}.}" loading="lazy">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=110}</annotation>

</semantics>

</math><img src="./c67af163dd96719cefee4bbd5e22aa0db31de685.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.676ex; height:2.176ex;" alt="{\displaystyle s=110}" loading="lazy"> can also be verified using input strings 001 and 111 that are both mapped (by f) to the same output string 010. Applying XOR to 001 and 111 obtains 110, that is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 001\oplus 111=110=s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 001\oplus 111=110=s}</annotation>

</semantics>

</math><img src="./ee2b2ce78daa99fa1003286eae70f0da4c86ce40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:20.59ex; height:2.343ex;" alt="{\displaystyle 001\oplus 111=110=s}" loading="lazy">. This gives the same solution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=110}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=110}</annotation>

</semantics>

</math><img src="./c67af163dd96719cefee4bbd5e22aa0db31de685.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.676ex; height:2.176ex;" alt="{\displaystyle s=110}" loading="lazy"> as before.

In this example the function f is indeed a two-to-one function where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\displaystyle s\neq 0^{n}}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\displaystyle s\neq 0^{n}}}</annotation>

</semantics>

</math><img src="./154122b07494a2a4d737b4b130322a0f289315f7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.57ex; height:2.843ex;" alt="{\displaystyle {\displaystyle s\neq 0^{n}}}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Problem_hardness">Problem hardness</h3></div>

Intuitively, this is a hard problem to solve in a "classical" way, even if one uses randomness and accepts a small probability of error. The intuition behind the hardness is reasonably simple: if you want to solve the problem classically, you need to find two different inputs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> for which <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)=f(y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)=f(y)}</annotation>

</semantics>

</math><img src="./7c45b4d507fbe420cf82e042d6f32f7aed7f8a12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.759ex; height:2.843ex;" alt="{\displaystyle f(x)=f(y)}" loading="lazy">. There is not necessarily any structure in the function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> that would help us to find two such inputs: more specifically, we can discover something about <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> (or what it does) only when, for two different inputs, we obtain the same output. In any case, we would need to guess <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\displaystyle \Omega ({\sqrt {2^{n}}})}}">

<msqrt>

<msup>

</mrow>

</msup>

</msqrt>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\displaystyle \Omega ({\sqrt {2^{n}}})}}</annotation>

</semantics>

</math><img src="./9d84d9b93a5fbab6c3bdd5aae3618c83ff5bebc8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.804ex; height:3.176ex;" alt="{\displaystyle {\displaystyle \Omega ({\sqrt {2^{n}}})}}" loading="lazy"> different inputs before being likely to find a pair on which <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> takes the same output, as per the <a href="Birthday_problem" title="Birthday problem">birthday problem</a>. Since, classically to find s with a 100% certainty it would require checking <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\displaystyle \Theta ({\sqrt {2^{n}}})}}">

<msqrt>

<msup>

</mrow>

</msup>

</msqrt>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\displaystyle \Theta ({\sqrt {2^{n}}})}}</annotation>

</semantics>

</math><img src="./fcfb5c87016289dc80d1b77cef298d7ecf2ec183.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.934ex; height:3.176ex;" alt="{\displaystyle {\displaystyle \Theta ({\sqrt {2^{n}}})}}" loading="lazy"> inputs, Simon's problem seeks to find s using fewer queries than this classical method.

<div class="mw-heading mw-heading2"><h2 id="Simon's_algorithm">Simon's algorithm</h2></div>

The algorithm as a whole uses a subroutine to execute the following two steps:

<ol><li>Run the quantum subroutine an expected <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy"> times to get a list of <a href="Linear_independence" title="Linear independence">linearly independent</a> bitstrings <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{1},...,y_{n-1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{1},...,y_{n-1}}</annotation>

</semantics>

</math><img src="./ef7d9b90c608f8b4a9d92412ec61ec87bd83e6b5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.821ex; height:2.009ex;" alt="{\displaystyle y_{1},...,y_{n-1}}" loading="lazy">.</li>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{k}}</annotation>

</semantics>

</math><img src="./4b2ab0248723a410cc2c67ce06ad5c043dcbb933.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.228ex; height:2.009ex;" alt="{\displaystyle y_{k}}" loading="lazy"> satisfies <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{k}\cdot s=0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{k}\cdot s=0}</annotation>

</semantics>

</math><img src="./4580452d1a495eff6341c995f6a8c46409a07ec6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.258ex; height:2.509ex;" alt="{\displaystyle y_{k}\cdot s=0}" loading="lazy">, so we can solve the system of equations this produces to get <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy">.</li></ol>

<div class="mw-heading mw-heading3"><h3 id="Quantum_subroutine">Quantum subroutine</h3></div>

The quantum circuit (see the picture) is the implementation of the quantum part of Simon's algorithm. The quantum subroutine of the algorithm makes use of the <a href="Hadamard_transform" title="Hadamard transform">Hadamard transform</a><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H^{\otimes n}|k\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{k\cdot j}|j\rangle }">

<msup>

</mrow>

</msup>

</mrow>

<mfrac>

<msqrt>

<msup>

</mrow>

</msup>

</msqrt>

</mfrac>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H^{\otimes n}|k\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{k\cdot j}|j\rangle }</annotation>

</semantics>

</math>where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\cdot j=k_{1}j_{1}\oplus \ldots \oplus k_{n}j_{n}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k\cdot j=k_{1}j_{1}\oplus \ldots \oplus k_{n}j_{n}}</annotation>

</semantics>

</math><img src="./1fe146bb3c23c243ca632f381603fef0f1c52804.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:24.235ex; height:2.509ex;" alt="{\displaystyle k\cdot j=k_{1}j_{1}\oplus \ldots \oplus k_{n}j_{n}}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \oplus }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \oplus }</annotation>

</semantics>

</math><img src="./8b16e2bdaefee9eed86d866e6eba3ac47c710f60.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \oplus }" loading="lazy"> denotes XOR.

First, the algorithm starts with two registers, initialized to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |0\rangle ^{\otimes n}|0\rangle ^{\otimes n}}">

</mrow>

<msup>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |0\rangle ^{\otimes n}|0\rangle ^{\otimes n}}</annotation>

</semantics>

</math><img src="./2fc10168a55f1ae1f87c17963fc059bad55099b4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.422ex; height:3.009ex;" alt="{\displaystyle |0\rangle ^{\otimes n}|0\rangle ^{\otimes n}}" loading="lazy">. Then, we apply the Hadamard transform to the first register, which gives the state

<mfrac>

<msqrt>

<msup>

</mrow>

</msup>

</msqrt>

</mfrac>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</munderover>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}|k\rangle |0\rangle ^{\otimes n}.}</annotation>

</semantics>

</math><img src="./0f9d1c2f21ae288e31112b3dadd74550b3afeaeb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:18.435ex; height:7.509ex;" alt="{\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}|k\rangle |0\rangle ^{\otimes n}.}" loading="lazy"></dd></dl>

Query the oracle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{f}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{f}}</annotation>

</semantics>

</math><img src="./f7be3c3c86d5d87a48bec069e8477dd5a4823fcc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.724ex; height:2.843ex;" alt="{\displaystyle U_{f}}" loading="lazy"> to get the state

<mfrac>

<msqrt>

<msup>

</mrow>

</msup>

</msqrt>

</mfrac>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</munderover>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}|k\rangle |f(k)\rangle }</annotation>

</semantics>

</math><img src="./9ba8a827702beb34324cce865c2f42976054b91c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:18.428ex; height:7.509ex;" alt="{\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}|k\rangle |f(k)\rangle }" loading="lazy">.</dd></dl>

Apply another Hadamard transform to the first register. This will produce the state

<mfrac>

<msqrt>

<msup>

</mrow>

</msup>

</msqrt>

</mfrac>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</munderover>

<mrow>

<mrow>

<mfrac>

<msqrt>

<msup>

</mrow>

</msup>

</msqrt>

</mfrac>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</munderover>

</mrow>

<mrow>

<mrow>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}\left[{\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{j\cdot k}|j\rangle \right]|f(k)\rangle =\sum _{j=0}^{2^{n}-1}|j\rangle \left[{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right].}</annotation>

</semantics>

</math><img src="./847a7b468c5c15ed2b3216f03f13618cd31d0f33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:72.063ex; height:7.676ex;" alt="{\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}\left[{\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{j\cdot k}|j\rangle \right]|f(k)\rangle =\sum _{j=0}^{2^{n}-1}|j\rangle \left[{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right].}" loading="lazy"> </dd></dl>

Finally, we measure the first register (the algorithm also works if the second register is measured before the first, but this is unnecessary). The probability of measuring a state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |j\rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |j\rangle }</annotation>

</semantics>

</math><img src="./3188b18f9e6f5b83f91e557f0e08a20e4bea3286.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.51ex; height:2.843ex;" alt="{\displaystyle |j\rangle }" loading="lazy"> is<math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}}">

<msup>

<mrow>

<mrow>

<mrow>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}}</annotation>

</semantics>

</math>This is due to the fact that taking the magnitude of this vector and squaring it sums up all the probabilities of all the possible measurements of the second register that must have the first register as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |j\rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |j\rangle }</annotation>

</semantics>

</math><img src="./3188b18f9e6f5b83f91e557f0e08a20e4bea3286.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.51ex; height:2.843ex;" alt="{\displaystyle |j\rangle }" loading="lazy">. There are two cases for our measurement:

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=0^{n}}</annotation>

</semantics>

</math><img src="./f54f4e79e802bec83e4d974c6065904b6d3e0f48.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.57ex; height:2.343ex;" alt="{\displaystyle s=0^{n}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is one-to-one.</li>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s\neq 0^{n}}</annotation>

</semantics>

</math><img src="./77677ccf3b43752c663efdb311dec341a3150d68.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.57ex; height:2.843ex;" alt="{\displaystyle s\neq 0^{n}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is two-to-one.</li></ol>

For the first case, <math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}={\frac {1}{2^{n}}}}">

<msup>

<mrow>

<mrow>

<mrow>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</msup>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}={\frac {1}{2^{n}}}}</annotation>

</semantics>

</math>since in this case, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is one-to-one, implying that the range of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{0,1\}^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{0,1\}^{n}}</annotation>

</semantics>

</math><img src="./3cc07e486d73e18382d0d8d205149f0923ed0586.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.902ex; height:2.843ex;" alt="{\displaystyle \{0,1\}^{n}}" loading="lazy">, meaning that the summation is over every basis vector. For the second case, note that there exist two strings, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1}}</annotation>

</semantics>

</math><img src="./a8788bf85d532fa88d1fb25eff6ae382a601c308.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{2}}</annotation>

</semantics>

</math><img src="./d7af1b928f06e4c7e3e8ebfd60704656719bd766.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{2}}" loading="lazy">, such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x_{1})=f(x_{2})=z}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x_{1})=f(x_{2})=z}</annotation>

</semantics>

</math><img src="./db2bbdfff713ab5a30823cca1f5274d71dc216a6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.229ex; height:2.843ex;" alt="{\displaystyle f(x_{1})=f(x_{2})=z}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z\in \mathrm {range} (f)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z\in \mathrm {range} (f)}</annotation>

</semantics>

</math><img src="./08498fdbfc4fa40082ebb9e21e303ef2519cf1ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.578ex; height:2.843ex;" alt="{\displaystyle z\in \mathrm {range} (f)}" loading="lazy">. Thus, <math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{2}})|z\rangle \right|\right|^{2}}">

<msup>

<mrow>

<mrow>

<mrow>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</msup>

<msup>

<mrow>

<mrow>

<mrow>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

</mrow>

</munder>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{2}})|z\rangle \right|\right|^{2}}</annotation>

</semantics>

</math>Furthermore, since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1}\oplus x_{2}=s}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1}\oplus x_{2}=s}</annotation>

</semantics>

</math><img src="./3f0822dbe36c31e03dea07077053fb4d66607687.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.797ex; height:2.343ex;" alt="{\displaystyle x_{1}\oplus x_{2}=s}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{2}=x_{1}\oplus s}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{2}=x_{1}\oplus s}</annotation>

</semantics>

</math><img src="./0c2e1ca725a08e2d9c5a97f8a9cb35b16b3df4d6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.797ex; height:2.343ex;" alt="{\displaystyle x_{2}=x_{1}\oplus s}" loading="lazy">, and so<math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{2}})|z\rangle \right|\right|^{2}&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot (x_{1}\oplus s)})|z\rangle \right|\right|^{2}\\&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{1}\oplus j\cdot s})|z\rangle \right|\right|^{2}\\&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}(-1)^{j\cdot x_{1}}(1+(-1)^{j\cdot s})|z\rangle \right|\right|^{2}\end{aligned}}}">

<mtr>

<mtd>

<msup>

<mrow>

<mrow>

<mrow>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

</mrow>

</munder>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</msup>

</mtd>

<mtd>

<msup>

<mrow>

<mrow>

<mrow>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

</mrow>

</munder>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

<mrow>

<mrow>

<mrow>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

</mrow>

</munder>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

<mrow>

<mrow>

<mrow>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

</mrow>

</munder>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</msup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{2}})|z\rangle \right|\right|^{2}&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot (x_{1}\oplus s)})|z\rangle \right|\right|^{2}\\&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{1}\oplus j\cdot s})|z\rangle \right|\right|^{2}\\&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}(-1)^{j\cdot x_{1}}(1+(-1)^{j\cdot s})|z\rangle \right|\right|^{2}\end{aligned}}}</annotation>

</semantics>

</math>This expression is now easy to evaluate. Recall that we are measuring <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy">. When <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j\cdot s=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j\cdot s=1}</annotation>

</semantics>

</math><img src="./59b2d4d96db9262337cd4c4894813c8eb87162ee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:8.015ex; height:2.509ex;" alt="{\displaystyle j\cdot s=1}" loading="lazy">, then this expression will evaluate to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy">, and when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j\cdot s=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j\cdot s=0}</annotation>

</semantics>

</math><img src="./c2eab908eaf45908275aa3804aaf73d6d9ac6acd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:8.015ex; height:2.509ex;" alt="{\displaystyle j\cdot s=0}" loading="lazy">, then this expression will be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{-n+1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{-n+1}}</annotation>

</semantics>

</math><img src="./706fd650e90ea62eb861b8c72b87b650580ca320.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.76ex; height:2.676ex;" alt="{\displaystyle 2^{-n+1}}" loading="lazy">.

Thus, both when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=0^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=0^{n}}</annotation>

</semantics>

</math><img src="./f54f4e79e802bec83e4d974c6065904b6d3e0f48.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.57ex; height:2.343ex;" alt="{\displaystyle s=0^{n}}" loading="lazy"> and when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s\neq 0^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s\neq 0^{n}}</annotation>

</semantics>

</math><img src="./77677ccf3b43752c663efdb311dec341a3150d68.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.57ex; height:2.843ex;" alt="{\displaystyle s\neq 0^{n}}" loading="lazy">, our measured <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"> satisfies <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j\cdot s=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j\cdot s=0}</annotation>

</semantics>

</math><img src="./c2eab908eaf45908275aa3804aaf73d6d9ac6acd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:8.015ex; height:2.509ex;" alt="{\displaystyle j\cdot s=0}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Classical_post-processing">Classical post-processing</h3></div>

We run the quantum part of the algorithm until we have a linearly independent list of bitstrings <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{1},\ldots ,y_{n-1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{1},\ldots ,y_{n-1}}</annotation>

</semantics>

</math><img src="./de383f5593a7fc0b4764f3883225d5640d6c4584.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.83ex; height:2.009ex;" alt="{\displaystyle y_{1},\ldots ,y_{n-1}}" loading="lazy">, and each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{k}}</annotation>

</semantics>

</math><img src="./4b2ab0248723a410cc2c67ce06ad5c043dcbb933.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.228ex; height:2.009ex;" alt="{\displaystyle y_{k}}" loading="lazy"> satisfies <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{k}\cdot s=0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{k}\cdot s=0}</annotation>

</semantics>

</math><img src="./4580452d1a495eff6341c995f6a8c46409a07ec6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.258ex; height:2.509ex;" alt="{\displaystyle y_{k}\cdot s=0}" loading="lazy">. Thus, we can efficiently solve this system of equations classically to find <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy">.

The probability that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{1},y_{2},\dots ,y_{n-1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{1},y_{2},\dots ,y_{n-1}}</annotation>

</semantics>

</math><img src="./a4f0516e729cb028b25985e429364870cea86503.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.057ex; height:2.009ex;" alt="{\displaystyle y_{1},y_{2},\dots ,y_{n-1}}" loading="lazy"> are linearly independent is at least<math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \prod _{k=1}^{\infty }\left(1-{\frac {1}{2^{k}}}\right)=0.288788\dots }">

</mrow>

</mrow>

</munderover>

<mrow>

<mrow>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \prod _{k=1}^{\infty }\left(1-{\frac {1}{2^{k}}}\right)=0.288788\dots }</annotation>

</semantics>

</math>Once we solve the system of equations, and produce a solution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s'}</annotation>

</semantics>

</math><img src="./5136680c63706cfd17ceddb4acddbfdd0ba5ef2d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.775ex; height:2.509ex;" alt="{\displaystyle s'}" loading="lazy">, we can test if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(0^{n})=f(s')}">

<msup>

</mrow>

</msup>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(0^{n})=f(s')}</annotation>

</semantics>

</math><img src="./2ce5cf2f7859cd7733f3df06cffaa203603991ac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.43ex; height:3.009ex;" alt="{\displaystyle f(0^{n})=f(s')}" loading="lazy">. If this is true, then we know <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s'=s}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s'=s}</annotation>

</semantics>

</math><img src="./6d5e32fc3e13efe39332708cea85423e7197b33c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.964ex; height:2.509ex;" alt="{\displaystyle s'=s}" loading="lazy">, since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(0^{n})=f(0^{n}\oplus s)=f(s)}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(0^{n})=f(0^{n}\oplus s)=f(s)}</annotation>

</semantics>

</math><img src="./35f2043e213188cdc39edc4868890078efa517fc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.244ex; height:2.843ex;" alt="{\displaystyle f(0^{n})=f(0^{n}\oplus s)=f(s)}" loading="lazy">. If it is the case that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(0^{n})\neq f(s')}">

<msup>

</mrow>

</msup>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(0^{n})\neq f(s')}</annotation>

</semantics>

</math><img src="./002daecc70845e08aece18ca9a01dd40f9f773ff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.43ex; height:3.009ex;" alt="{\displaystyle f(0^{n})\neq f(s')}" loading="lazy">, then that means that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=0^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=0^{n}}</annotation>

</semantics>

</math><img src="./f54f4e79e802bec83e4d974c6065904b6d3e0f48.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.57ex; height:2.343ex;" alt="{\displaystyle s=0^{n}}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(0^{n})\neq f(s')}">

<msup>

</mrow>

</msup>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(0^{n})\neq f(s')}</annotation>

</semantics>

</math><img src="./002daecc70845e08aece18ca9a01dd40f9f773ff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.43ex; height:3.009ex;" alt="{\displaystyle f(0^{n})\neq f(s')}" loading="lazy"> since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is one-to-one.

We can repeat Simon's algorithm a constant number of times to increase the probability of success arbitrarily, while still having the same time complexity.

<div class="mw-heading mw-heading2"><h2 id="Explicit_examples_of_Simon's_algorithm_for_few_qubits">Explicit examples of Simon's algorithm for few qubits</h2></div>

<div class="mw-heading mw-heading3"><h3 id="One_qubit">One qubit</h3></div>

Consider the simplest instance of the algorithm, with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=1}</annotation>

</semantics>

</math><img src="./d9ec7e1edc2e6d98f5aec2a39ae5f1c99d1e1425.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.656ex; height:2.176ex;" alt="{\displaystyle n=1}" loading="lazy">. In this case evolving the input state through an Hadamard gate and the oracle results in the state (up to renormalization):

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |0\rangle |f(0)\rangle +|1\rangle |f(1)\rangle .}</annotation>

</semantics>

</math><img src="./a04462d4d5897aebc1780aa5df8b7d271b96d8e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.519ex; height:2.843ex;" alt="{\displaystyle |0\rangle |f(0)\rangle +|1\rangle |f(1)\rangle .}" loading="lazy"></dd></dl>

If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=1}</annotation>

</semantics>

</math><img src="./bac386d8f227fb823cede9b3e33d706cad3ed306.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.351ex; height:2.176ex;" alt="{\displaystyle s=1}" loading="lazy">, that is, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(0)=f(1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(0)=f(1)}</annotation>

</semantics>

</math><img src="./cc37ee05542c1472c465dd6441c3d3a8a1adfa6d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.599ex; height:2.843ex;" alt="{\displaystyle f(0)=f(1)}" loading="lazy">, then measuring the second register always gives the outcome <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |f(0)\rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |f(0)\rangle }</annotation>

</semantics>

</math><img src="./39e17c11e7a8547c98cbdc41a41956e90144f187.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.802ex; height:2.843ex;" alt="{\displaystyle |f(0)\rangle }" loading="lazy">, and always results in the first register collapsing to the state (up to renormalization):

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |0\rangle +|1\rangle .}</annotation>

</semantics>

</math><img src="./92f3b24b132a28dec7c8feac8e82b8ad946956ae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.915ex; height:2.843ex;" alt="{\displaystyle |0\rangle +|1\rangle .}" loading="lazy"></dd></dl>

Thus applying an Hadamard and measuring the first register always gives the outcome <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |0\rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |0\rangle }</annotation>

</semantics>

</math><img src="./ed066a3ad158da0ad6d6a421a606b1c8a35eb95b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.714ex; height:2.843ex;" alt="{\displaystyle |0\rangle }" loading="lazy">. On the other hand, if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is one-to-one, that is, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=0}</annotation>

</semantics>

</math><img src="./7903b8069a44c70f6f96511675bdd9a4ff200ed7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.351ex; height:2.176ex;" alt="{\displaystyle s=0}" loading="lazy">, then measuring the first register after the second Hadamard can result in both <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |0\rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |0\rangle }</annotation>

</semantics>

</math><img src="./ed066a3ad158da0ad6d6a421a606b1c8a35eb95b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.714ex; height:2.843ex;" alt="{\displaystyle |0\rangle }" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |1\rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |1\rangle }</annotation>

</semantics>

</math><img src="./2f53021ca18e77477ee5bd3c1523e5830189ec5c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.714ex; height:2.843ex;" alt="{\displaystyle |1\rangle }" loading="lazy">, with equal probability.

We recover <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> from the measurement outcomes by looking at whether we measured always <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |0\rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |0\rangle }</annotation>

</semantics>

</math><img src="./ed066a3ad158da0ad6d6a421a606b1c8a35eb95b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.714ex; height:2.843ex;" alt="{\displaystyle |0\rangle }" loading="lazy">, in which case <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=1}</annotation>

</semantics>

</math><img src="./bac386d8f227fb823cede9b3e33d706cad3ed306.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.351ex; height:2.176ex;" alt="{\displaystyle s=1}" loading="lazy">, or we measured both <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |0\rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |0\rangle }</annotation>

</semantics>

</math><img src="./ed066a3ad158da0ad6d6a421a606b1c8a35eb95b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.714ex; height:2.843ex;" alt="{\displaystyle |0\rangle }" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |1\rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |1\rangle }</annotation>

</semantics>

</math><img src="./2f53021ca18e77477ee5bd3c1523e5830189ec5c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.714ex; height:2.843ex;" alt="{\displaystyle |1\rangle }" loading="lazy"> with equal probability, in which case we infer that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=0}</annotation>

</semantics>

</math><img src="./7903b8069a44c70f6f96511675bdd9a4ff200ed7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.351ex; height:2.176ex;" alt="{\displaystyle s=0}" loading="lazy">. This scheme will fail if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=0}</annotation>

</semantics>

</math><img src="./7903b8069a44c70f6f96511675bdd9a4ff200ed7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.351ex; height:2.176ex;" alt="{\displaystyle s=0}" loading="lazy"> but we nonetheless always found the outcome <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |0\rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |0\rangle }</annotation>

</semantics>

</math><img src="./ed066a3ad158da0ad6d6a421a606b1c8a35eb95b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.714ex; height:2.843ex;" alt="{\displaystyle |0\rangle }" loading="lazy">, but the probability of this event is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{-N}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{-N}}</annotation>

</semantics>

</math><img src="./842b0ef6cc28e9e7e4bf3d4a8f999ea8fc6afd04.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.132ex; height:2.676ex;" alt="{\displaystyle 2^{-N}}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> the number of performed measurements, and can thus be made exponentially small by increasing the statistics.

<div class="mw-heading mw-heading3"><h3 id="Two_qubits">Two qubits</h3></div>

Consider now the case with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=2}</annotation>

</semantics>

</math><img src="./a02c8bd752d2cc859747ca1f3a508281bdbc3b34.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.656ex; height:2.176ex;" alt="{\displaystyle n=2}" loading="lazy">. The initial part of the algorithm results in the state (up to renormalization):<math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |00\rangle |f(00)\rangle +|01\rangle |f(01)\rangle +|10\rangle |f(10)\rangle +|11\rangle |f(11)\rangle .}">

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |00\rangle |f(00)\rangle +|01\rangle |f(01)\rangle +|10\rangle |f(10)\rangle +|11\rangle |f(11)\rangle .}</annotation>

</semantics>

</math>If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=(00)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=(00)}</annotation>

</semantics>

</math><img src="./a5d304ab8065486fd77a7de6f7620f6f09fb404d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.323ex; height:2.843ex;" alt="{\displaystyle s=(00)}" loading="lazy">, meaning <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is injective, then finding <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |f(x)\rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |f(x)\rangle }</annotation>

</semantics>

</math><img src="./50fc4f686cc08acae5e6c36dc41b9d0222621f7e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.969ex; height:2.843ex;" alt="{\displaystyle |f(x)\rangle }" loading="lazy"> on the second register always collapses the first register to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |x\rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |x\rangle }</annotation>

</semantics>

</math><img src="./48004887d8f9dfc489bd2bc793780b7f1d8039ad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.881ex; height:2.843ex;" alt="{\displaystyle |x\rangle }" loading="lazy">, for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in \{0,1\}^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in \{0,1\}^{2}}</annotation>

</semantics>

</math><img src="./f92cbcf6220d2a2d0945d1bfd74aa86cf18d2b69.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.908ex; height:3.176ex;" alt="{\displaystyle x\in \{0,1\}^{2}}" loading="lazy">. In other words, applying Hadamard gates and measuring the first register the four outcomes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 00,01,10,11}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 00,01,10,11}</annotation>

</semantics>

</math><img src="./3cc6aebb06f4611bb3835100b5f0ccd846cd73af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.401ex; height:2.509ex;" alt="{\displaystyle 00,01,10,11}" loading="lazy"> are thus found with equal probability.

Suppose on the other hand <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s\neq (00)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s\neq (00)}</annotation>

</semantics>

</math><img src="./8b0fae6f3b493e7ce7158f049709fa172018ef13.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.323ex; height:2.843ex;" alt="{\displaystyle s\neq (00)}" loading="lazy">, for example, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=(01)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=(01)}</annotation>

</semantics>

</math><img src="./fd829b3a58904f7be3fe9a096d0740e398e34c4b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.323ex; height:2.843ex;" alt="{\displaystyle s=(01)}" loading="lazy">. Then measuring <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |f(00)\rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |f(00)\rangle }</annotation>

</semantics>

</math><img src="./4c459b1f4fffbe318d49019e9fdc688e4503ed5b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.964ex; height:2.843ex;" alt="{\displaystyle |f(00)\rangle }" loading="lazy"> on the second register collapses the first register to the state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |00\rangle +|10\rangle }">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |00\rangle +|10\rangle }</annotation>

</semantics>

</math><img src="./ad512b846406299705b6a74136ae41b9c5c192b4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.593ex; height:2.843ex;" alt="{\displaystyle |00\rangle +|10\rangle }" loading="lazy">. And more generally, measuring <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |f(xy)\rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |f(xy)\rangle }</annotation>

</semantics>

</math><img src="./e4d04c74eef4fff142524b5e18dcb49c4aa2fa33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.125ex; height:2.843ex;" alt="{\displaystyle |f(xy)\rangle }" loading="lazy"> gives <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |x,y\rangle +|x,y\oplus 1\rangle =|x\rangle (|0\rangle +|1\rangle )}">

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |x,y\rangle +|x,y\oplus 1\rangle =|x\rangle (|0\rangle +|1\rangle )}</annotation>

</semantics>

</math><img src="./0b621e1615d9b81aa9a96d4a4f3d5e83b7df1ee2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.042ex; height:2.843ex;" alt="{\displaystyle |x,y\rangle +|x,y\oplus 1\rangle =|x\rangle (|0\rangle +|1\rangle )}" loading="lazy"> on the first register. Applying Hadamard gates and measuring on the first register can thus result in the outcomes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 00}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 00}</annotation>

</semantics>

</math><img src="./f2ceb80fb1bce390c5819835569f4a5df37290ee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.325ex; height:2.176ex;" alt="{\displaystyle 00}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 10}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 10}</annotation>

</semantics>

</math><img src="./4ec811eb07dcac7ea67b413c5665390a1671ecb0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.325ex; height:2.176ex;" alt="{\displaystyle 10}" loading="lazy"> with equal probabilities.

Similar reasoning applies to the other cases: if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=(10)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=(10)}</annotation>

</semantics>

</math><img src="./30e32d7416b2cfb0a4b158c7dacee5bdf0a0cdcb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.323ex; height:2.843ex;" alt="{\displaystyle s=(10)}" loading="lazy"> then the possible outcomes are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 00}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 00}</annotation>

</semantics>

</math><img src="./f2ceb80fb1bce390c5819835569f4a5df37290ee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.325ex; height:2.176ex;" alt="{\displaystyle 00}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 01}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 01}</annotation>

</semantics>

</math><img src="./ac8deb85e579248e3f9c4f3cef7ee37f9d3769d8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.325ex; height:2.176ex;" alt="{\displaystyle 01}" loading="lazy">, while if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=(11)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=(11)}</annotation>

</semantics>

</math><img src="./d5b4e3a3da08b8fe85c8fc2e6587c37a7e124e3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.323ex; height:2.843ex;" alt="{\displaystyle s=(11)}" loading="lazy"> the possible outcomes are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 00}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 00}</annotation>

</semantics>

</math><img src="./f2ceb80fb1bce390c5819835569f4a5df37290ee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.325ex; height:2.176ex;" alt="{\displaystyle 00}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 11}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 11}</annotation>

</semantics>

</math><img src="./da6aabe7c6af49fe640b2d401cb2dbe909bb7475.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.325ex; height:2.176ex;" alt="{\displaystyle 11}" loading="lazy">, compatibly with the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j\cdot s=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j\cdot s=0}</annotation>

</semantics>

</math><img src="./c2eab908eaf45908275aa3804aaf73d6d9ac6acd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:8.015ex; height:2.509ex;" alt="{\displaystyle j\cdot s=0}" loading="lazy"> rule discussed in the general case.

To recover <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> we thus only need to distinguish between these four cases, collecting enough statistics to ensure that the probability of mistaking one outcome probability distribution for another is sufficiently small.

<div class="mw-heading mw-heading2"><h2 id="Complexity">Complexity</h2></div>

Simon's algorithm requires <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy"> queries to the black box, whereas a classical algorithm would need at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (2^{n/2})}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (2^{n/2})}</annotation>

</semantics>

</math><img src="./bc79b0c9a96cb7891d043f44ac450441d33a211f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.512ex; height:3.343ex;" alt="{\displaystyle \Omega (2^{n/2})}" loading="lazy"> queries. It is also known that Simon's algorithm is optimal in the sense that any quantum algorithm to solve this problem requires <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (n)}</annotation>

</semantics>

</math><img src="./6becc31c61ad3420a1e4ee9e39c28baf73bda24d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.882ex; height:2.843ex;" alt="{\displaystyle \Omega (n)}" loading="lazy"> queries.<a href="#cite_note-5">[5]</a><a href="#cite_note-6">[6]</a>

<div class="mw-heading mw-heading2"><h2 id="Simon's_algorithm_Qiskit_implementation">Simon's algorithm Qiskit implementation</h2></div>

The quantum circuit shown here is from <a rel="nofollow" class="external text" href="https://learning.quantum.ibm.com/course/fundamentals-of-quantum-algorithms/quantum-query-algorithms#simons-algorithm">a simple example of how Simon's algorithm can be implemented in Python</a> using <a href="Qiskit" title="Qiskit">Qiskit</a>, an open-source quantum computing software development framework by IBM.

<ul><li><a href="Deutsch%E2%80%93Jozsa_algorithm" title="Deutsch–Jozsa algorithm">Deutsch–Jozsa algorithm</a></li>

<li><a href="Shor's_algorithm" title="Shor's algorithm">Shor's algorithm</a></li>

<li><a href="Bernstein%E2%80%93Vazirani_algorithm" title="Bernstein–Vazirani algorithm">Bernstein–Vazirani algorithm</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFShor1999" class="citation journal cs1">Shor, Peter W. (1999-01-01). <a rel="nofollow" class="external text" href="https://epubs.siam.org/doi/10.1137/S0036144598347011">"Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer"</a>. SIAM Review. 41 (2): 303–332. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/9508027">quant-ph/9508027</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0036144598347011">10.1137/S0036144598347011</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0036-1445">0036-1445</a>.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFSimon1997" class="citation journal cs1">Simon, Daniel R. (1997-10-01). <a rel="nofollow" class="external text" href="https://epubs.siam.org/doi/10.1137/S0097539796298637">"On the Power of Quantum Computation"</a>. SIAM Journal on Computing. 26 (5): 1474–1483. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0097539796298637">10.1137/S0097539796298637</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0097-5397">0097-5397</a>.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFPreskill1998" class="citation book cs1">Preskill, John (1998). <a rel="nofollow" class="external text" href="http://theory.caltech.edu/~preskill/ph229/">Lecture Notes for Physics 229: Quantum Information and Computation</a>. pp. 273–275.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFAaronson2018" class="citation book cs1">Aaronson, Scott (2018). <a rel="nofollow" class="external text" href="https://www.scottaaronson.com/qclec.pdf">Introduction to Quantum Information Science Lecture Notes</a> (PDF). pp. 144–151.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFKoiranNesmePortier2007" class="citation cs2">Koiran, P.; Nesme, V.; Portier, N. (2007), <a rel="nofollow" class="external text" href="http://perso.ens-lyon.fr/pascal.koiran/Publis/lip.05-17.ps">"The quantum query complexity of the Abelian hidden subgroup problem"</a>, Theoretical Computer Science, 380 (1–2): 115–126, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.tcs.2007.02.057">10.1016/j.tcs.2007.02.057</a>, retrieved 2011-06-06</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFKoiranNesmePortier2005" class="citation cs2">Koiran, P.; Nesme, V.; Portier, N. (2005), <a rel="nofollow" class="external text" href="http://perso.ens-lyon.fr/pascal.koiran/Publis/icalp05.ps">"A quantum lower bound for the query complexity of Simon's Problem"</a>, Proc. ICALP, 3580: 1287–1298, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/0501060">quant-ph/0501060</a>, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2005quant.ph..1060K">2005quant.ph..1060K</a>, retrieved 2011-06-06</cite>

</li>

</ol></div></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Quantum_information_science667" style="padding:3px"><table class="nowraplinks hlist mw-collapsible mw-collapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Quantum_information_science667" style="font-size:114%;margin:0 4em"><a href="Quantum_information_science" title="Quantum information science">Quantum information science</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="DiVincenzo's_criteria" title="DiVincenzo's criteria">DiVincenzo's criteria</a></li>

<li><a href="Quantum_computing" title="Quantum computing">Quantum computing</a>

<ul><li><a href="Timeline_of_quantum_computing_and_communication" title="Timeline of quantum computing and communication">timeline</a></li></ul></li>

<li><a href="Quantum_information" title="Quantum information">Quantum information</a></li>

<li><a href="Quantum_programming" title="Quantum programming">Quantum programming</a></li>

<li><a href="Quantum_simulator" title="Quantum simulator">Quantum simulation</a></li>

<li><a href="Qubit" title="Qubit">Qubit</a>

<ul><li><a href="Physical_and_logical_qubits" title="Physical and logical qubits">physical vs. logical</a></li></ul></li>

<li><a href="List_of_quantum_processors" title="List of quantum processors">Quantum processors</a>

<ul><li><a href="Cloud-based_quantum_computing" title="Cloud-based quantum computing">cloud-based</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Theorems</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Eastin%E2%80%93Knill_theorem" title="Eastin–Knill theorem">Eastin–Knill</a></li>

<li><a href="Gleason's_theorem" title="Gleason's theorem">Gleason's</a></li>

<li><a href="Gottesman%E2%80%93Knill_theorem" title="Gottesman–Knill theorem">Gottesman–Knill</a></li>

<li><a href="Holevo's_theorem" title="Holevo's theorem">Holevo's</a></li>

<li><a href="No-broadcasting_theorem" title="No-broadcasting theorem">No-broadcasting</a></li>

<li><a href="No-cloning_theorem" title="No-cloning theorem">No-cloning</a></li>

<li><a href="No-communication_theorem" title="No-communication theorem">No-communication</a></li>

<li><a href="No-deleting_theorem" title="No-deleting theorem">No-deleting</a></li>

<li><a href="No-hiding_theorem" title="No-hiding theorem">No-hiding</a></li>

<li><a href="No-teleportation_theorem" title="No-teleportation theorem">No-teleportation</a></li>

<li><a href="Quantum_speed_limit_theorems" class="mw-redirect" title="Quantum speed limit theorems">Quantum speed limit</a></li>

<li><a href="Threshold_theorem" title="Threshold theorem">Threshold</a></li>

<li><a href="Solovay%E2%80%93Kitaev_theorem" title="Solovay–Kitaev theorem">Solovay–Kitaev</a></li>

<li><a href="Schr%C3%B6dinger%E2%80%93HJW_theorem" class="mw-redirect" title="Schrödinger–HJW theorem">Schrödinger-HJW</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Quantum communication</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Classical_capacity" title="Classical capacity">Classical capacity</a>

<ul><li><a href="Entanglement-assisted_classical_capacity" title="Entanglement-assisted classical capacity">entanglement-assisted</a></li>

<li><a href="Quantum_capacity" title="Quantum capacity">quantum capacity</a></li></ul></li>

<li><a href="Entanglement_distillation" title="Entanglement distillation">Entanglement distillation</a></li>

<li><a href="Entanglement_swapping" title="Entanglement swapping">Entanglement swapping</a></li>

<li><a href="Monogamy_of_entanglement" title="Monogamy of entanglement">Monogamy of entanglement</a></li>

<li><a href="Quantum_channel" title="Quantum channel">Quantum channel</a>

<ul><li><a href="Quantum_network" title="Quantum network">quantum network</a></li></ul></li>

<li><a href="Quantum_state_purification" title="Quantum state purification">State purification</a></li>

<li><a href="Quantum_teleportation" title="Quantum teleportation">Quantum teleportation</a>

<ul><li><a href="Quantum_energy_teleportation" title="Quantum energy teleportation">quantum energy teleportation</a></li>

<li><a href="Quantum_gate_teleportation" title="Quantum gate teleportation">quantum gate teleportation</a></li></ul></li>

<li><a href="Superdense_coding" title="Superdense coding">Superdense coding</a></li></ul>

</div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Quantum_cryptography24" scope="row" class="navbox-group" style="width:1%"><a href="Quantum_cryptography" title="Quantum cryptography">Quantum cryptography</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Post-quantum_cryptography" title="Post-quantum cryptography">Post-quantum cryptography</a></li>

<li><a href="Quantum_coin_flipping" title="Quantum coin flipping">Quantum coin flipping</a></li>

<li><a href="Quantum_money" title="Quantum money">Quantum money</a></li>

<li><a href="Quantum_key_distribution" title="Quantum key distribution">Quantum key distribution</a>

<li><a href="List_of_quantum_key_distribution_protocols" title="List of quantum key distribution protocols">other protocols</a></li></ul></li>

<li><a href="Quantum_secret_sharing" title="Quantum secret sharing">Quantum secret sharing</a></li></ul>

</div></td></tr></tbody></table><div>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quantum_algorithm" title="Quantum algorithm">Quantum algorithms</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Algorithmic_cooling" title="Algorithmic cooling">Algorithmic cooling</a></li>

<li><a href="Amplitude_amplification" title="Amplitude amplification">Amplitude amplification</a></li>

<li><a href="Bernstein%E2%80%93Vazirani_algorithm" title="Bernstein–Vazirani algorithm">Bernstein–Vazirani</a></li>

<li><a href="Boson_sampling" title="Boson sampling">Boson sampling</a></li>

<li><a href="Deutsch%E2%80%93Jozsa_algorithm" title="Deutsch–Jozsa algorithm">Deutsch–Jozsa</a></li>

<li><a href="Grover's_algorithm" title="Grover's algorithm">Grover's</a></li>

<li><a href="Hidden_subgroup_problem" title="Hidden subgroup problem">Hidden subgroup</a></li>

<li><a href="Magic_state_distillation" title="Magic state distillation">Magic state distillation</a></li>

<li><a href="Quantum_annealing" title="Quantum annealing">Quantum annealing</a></li>

<li><a href="Quantum_counting_algorithm" title="Quantum counting algorithm">Quantum counting</a></li>

<li><a href="Quantum_Fourier_transform" title="Quantum Fourier transform">Quantum Fourier transform</a></li>

<li><a href="Quantum_optimization_algorithms" title="Quantum optimization algorithms">Quantum optimization</a></li>

<li><a href="Quantum_phase_estimation_algorithm" title="Quantum phase estimation algorithm">Quantum phase estimation</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quantum_complexity_theory" title="Quantum complexity theory">Quantum complexity theory</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="PostBQP" title="PostBQP">PostBQP</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Quantum processor benchmarks</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Quantum_supremacy" title="Quantum supremacy">Quantum supremacy</a></li>

<li><a href="Quantum_volume" title="Quantum volume">Quantum volume</a></li>

<li><a href="Randomized_benchmarking" title="Randomized benchmarking">Randomized benchmarking</a>

<li><a href="Relaxation_(NMR)" title="Relaxation (NMR)">Relaxation times</a>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Quantum <a href="Model_of_computation" title="Model of computation">computing models</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Adiabatic_quantum_computation" title="Adiabatic quantum computation">Adiabatic quantum computation</a></li>

<li><a href="Continuous-variable_quantum_information" title="Continuous-variable quantum information">Continuous-variable quantum information</a></li>

<li><a href="One-way_quantum_computer" title="One-way quantum computer">One-way quantum computer</a>

<ul><li><a href="Cluster_state" title="Cluster state">cluster state</a></li></ul></li>

<li><a href="Quantum_circuit" title="Quantum circuit">Quantum circuit</a>

<ul><li><a href="Quantum_logic_gate" title="Quantum logic gate">quantum logic gate</a></li></ul></li>

<li><a href="Quantum_machine_learning" title="Quantum machine learning">Quantum machine learning</a>

<ul><li><a href="Quantum_neural_network" title="Quantum neural network">quantum neural network</a></li></ul></li>

<li><a href="Quantum_Turing_machine" title="Quantum Turing machine">Quantum Turing machine</a></li>

<li><a href="Topological_quantum_computer" title="Topological quantum computer">Topological quantum computer</a></li>

<li><a href="Hamiltonian_quantum_computation" title="Hamiltonian quantum computation">Hamiltonian quantum computation</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quantum_error_correction" title="Quantum error correction">Quantum error correction</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li>Codes

<ul><li><a href="Five-qubit_error_correcting_code" title="Five-qubit error correcting code">5 qubit</a></li>

<li><a href="Quantum_convolutional_code" title="Quantum convolutional code">quantum convolutional</a></li>

<li><a href="Stabilizer_code" title="Stabilizer code">stabilizer</a></li>

<li><a href="Bacon%E2%80%93Shor_code" title="Bacon–Shor code">Bacon–Shor</a></li>

<li><a href="Steane_code" title="Steane code">Steane</a></li>

<li><a href="Toric_code" title="Toric code">Toric</a></li>

<li><a href="Entanglement-assisted_stabilizer_formalism" title="Entanglement-assisted stabilizer formalism">Entanglement-assisted</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Physical implementations</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quantum_optics" title="Quantum optics">Quantum optics</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Cavity_quantum_electrodynamics" title="Cavity quantum electrodynamics">Cavity QED</a></li>

<li><a href="Circuit_quantum_electrodynamics" title="Circuit quantum electrodynamics">Circuit QED</a></li>

<li><a href="Linear_optical_quantum_computing" title="Linear optical quantum computing">Linear optical QC</a></li>

<li><a href="KLM_protocol" title="KLM protocol">KLM protocol</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Ultracold_atom" title="Ultracold atom">Ultracold atoms</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Neutral_atom_quantum_computer" title="Neutral atom quantum computer">Neutral atom QC</a></li>

<li><a href="Trapped-ion_quantum_computer" title="Trapped-ion quantum computer">Trapped-ion QC</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Spin_(physics)" title="Spin (physics)">Spin</a>-based</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Spin_qubit_quantum_computer" title="Spin qubit quantum computer">Spin qubit QC</a></li>

<li><a href="Nitrogen-vacancy_center" title="Nitrogen-vacancy center">NV center</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Superconducting_quantum_computing" title="Superconducting quantum computing">Superconducting</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Charge_qubit" title="Charge qubit">Charge qubit</a></li>

<li><a href="Flux_qubit" title="Flux qubit">Flux qubit</a></li>

<li><a href="Phase_qubit" title="Phase qubit">Phase qubit</a></li>

<li><a href="Transmon" title="Transmon">Transmon</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quantum_programming" title="Quantum programming">Quantum programming</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="OpenQASM" title="OpenQASM">OpenQASM</a>–<a href="Qiskit" title="Qiskit">Qiskit</a>–<a href="IBM_Quantum_Experience" class="mw-redirect" title="IBM Quantum Experience">IBM QX</a></li>

<li><a href="Quil_(instruction_set_architecture)" title="Quil (instruction set architecture)">Quil</a>–<a href="Rigetti_Computing" title="Rigetti Computing">Forest/Rigetti QCS</a></li>

<li><a href="Libquantum" title="Libquantum">libquantum</a></li>

<li><a href="Quantum_programming" title="Quantum programming">many others...</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li> Quantum information science</li>

<li> Quantum mechanics topics</li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-24" href="https://en.wikipedia.org/wiki/?title=Simon's_problem&oldid=1291965572">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>